package com.ifish.leetcode.problem.algorithm;

import com.ifish.leetcode.problem.BaseLeetCodeProblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by iFish on 2017/7/17.
 */

// Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

public class _0015 extends BaseLeetCodeProblem {
    @Override
    public String title() {
        return "3Sum";
    }

    @Override
    public int difficulty() {
        return 1;
    }

    @Override
    public void run() {
        super.run();

//        int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
        int nums[] = new int[]{0,0,0,0};
        List<List<Integer>> result = threeSum(nums);

    }

    // 超时。。

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        if (len >= 3) {
            for (int i = 0; i < len - 2; i++) {
                int n1 = nums[i];
                if (i > 0 && n1 == nums[i - 1]) continue;
                for (int j = i + 1; j < len - 1; j++) {
                    int n2 = nums[j];
                    if (j > i + 1 && n2 == nums[j - 1]) continue;
                    for (int k = j + 1; k < len; k++) {
                        int n3 = nums[k];
                        if (k > j + 1 && n3 == nums[k - 1]) continue;
                        if (n1 + n2 + n3 == 0) {
                            result.add(Arrays.asList(n1, n2, n3));
                        }
                    }
                }
            }
        }
        return result;
    }
}
